package com.algorithm.liyc.greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 0056.合并区间
 * 给出一个区间的集合，请合并所有重叠的区间。
 *
 * @author Liyc
 * @date 2024/1/30 9:33
 **/

public class Solution15 {
    /**
     * 时间复杂度 ： O(NlogN) 排序需要O(NlogN)
     * 空间复杂度 ： O(logN)  java 的内置排序是快速排序 需要 O(logN)空间
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        //按照左边界排序
        Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));
        //initial start 是最小左边界
        int start = intervals[0][0];
        int rightMax = intervals[0][1];
        LinkedList<int[]> res = new LinkedList<>();
        for (int i = 1; i < intervals.length; i++) {
            //如果左边界大于最大右边界
            if (intervals[i][0] > rightMax) {
                //加入区间 并且更新start
                res.add(new int[]{start, rightMax});
                start = intervals[i][0];
                rightMax = intervals[i][1];
            } else {
                //更新最大右边界
                rightMax = Math.max(rightMax, intervals[i][1]);
            }
        }
        //加入最后的区间
        res.add(new int[]{start, rightMax});
        return res.toArray(new int[res.size()][]);
    }
}
